//时间复杂度O(n^2)
class Solution {
public:
    int jump(vector<int>& nums) {
        int position = nums.size() - 1;
        int steps = 0;
        while (position > 0) {
            for (int i = 0; i < position; i++) {
                if (i + nums[i] >= position) {
                    position = i;
                    steps++;
                    break;
                }
            }
        }
        return steps;
    }
};

//时间复杂度O(n)
class Solution {
public:
    int jump(vector<int>& nums) {
        //2.
        int start = 0;
        int end = 0;
        int farthest = 0;
        int steps = 0;
        while(farthest < nums.size()-1)
        {
            ++steps;
            for(int i = start;i <= end;++i)
            {
                farthest = std::max(farthest,i + nums[i]);
                if(farthest >= nums.size()-1) //优化，下一跳的位置超过或等于数组的最后一个元素的位置，则退出
                break;
            }

            if(farthest == end){ //判断最终能不能跳到数组最后一个元素的位置
                return -1;
            }

            start = end + 1;
            end = farthest;
        }
        return steps;
}